int isPrime[maxn], primes[maxn], totprimes, mu[maxn], phi[maxn];

void linearShai() {
	mu[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		if (isPrime[i]) {
			primes[totprimes ++] = i;
			mu[i] = -1;
			phi[i] = i - 1;
		}
		for (int j = 0; j < totprimes && i * primes[j] <= n; ++ j) {
			isPrime[i * primes[j]] = 0;
			if (i % primes[j] == 0) {
				mu[i * primes[j]] = 0;
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			} else {
				mu[i * primes[j]] = -mu[i];
				phi[i * primes[j]] = phi[i] * (primes[j] - 1);
			}
		}
	}
}
